/**
        * 给你一个字符串 s，找到 s 中最长的回文子串。
        *
        *https://leetcode.cn/problems/longest-palindromic-substring/
        */
class LongestPalindromeDonGui {
    /**
     * 法一：动态规划
     * @param s
     * @return
     */
    public String longestPalindromeDonGui(String s) {
        int index1=0;
        int index2=0;
        int max=1;
        int len=s.length();
        boolean[][] isPail=new boolean[len][len];
        for(int i=len-1;i>=0;i--) {
            for(int j=i;j<len;j++) {
                if(j==i) {
                    isPail[i][j]=true;
                    
                } else if(i+1==j) {
                    if(s.charAt(i)==s.charAt(j)) {
                        isPail[i][j]=true;
                    } else {
                        isPail[i][j]=false;
                    }
                } else {
                    isPail[i][j]=(s.charAt(i)==s.charAt(j)&&isPail[i+1][j-1]);
                }
                if(isPail[i][j]&&j-i+1>max) {
                    max=j-i+1;
                    index1=i;
                    index2=j;
                }
            }
        }
        return s.substring(index1,index2+1);
    }
    /**
     * 法二：双指针解法
     * 寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串，对于最长回文子串，就是这个意思：
     * 找回文串的关键技巧是传入两个指针 l 和 r 向两边扩散，因为这样实现可以同时处理回文串长度为奇数和偶数的情况。
     * @param s
     * @return
     */
    public String longestPalindromeDoublePoint(String s) {
        String res="";
        int len=s.length();
        for(int i=0;i<len;i++) {
            /// 找到以 s[i] 为中心的回文串
            String s1=palindrome(s,i,i);
            // 找到以 s[i] 和 s[i+1] 为中心的回文串
            String s2=palindrome(s,i,i+1);
            // 更新答案
            res=s1.length()>res.length()?s1:res;
            res=s2.length()>res.length()?s2:res;
        }
        return res;
    }
    public String palindrome(String s,int l,int r) {
        int len=s.length();
        //防止索引越界
        while(l>=0&&r<len&&s.charAt(l)==s.charAt(r)) {
            //双指针向两边展开
            l--;
            r++;
        }
        return s.substring(l+1,r);
    }
}